//
// Created by Administrator on 2021/11/9.
// May Saint Diana bless you!
//
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxCoins(vector<int> &piles) {
        // 先排序
        sort(piles.begin(), piles.end());
        // 每次，拿出最小的给Bob，再拿出最大的两个，自己可以拿其中较小的那一个
        int i = 0, j = (int) piles.size() - 1;
        int ans = 0;
        while (i<j){
            ++i; // Bob拿最小的
            --j; // Alice拿走
            ans += piles[j];// 自己拿走
            --j;
        }
        return ans;
    }
    int maxCoins2(vector<int>& piles) {
        sort(piles.begin(), piles.end());
        int length = piles.size();
        int rounds = length / 3;
        int coins = 0;
        int index = length - 2;
        for (int i = 0; i < rounds; i++) {
            coins += piles[index];
            index -= 2;
        }
        return coins;
    }

};

int main() {
    vector<int> piles{9,8,7,6,5,1,2,3,4};
    Solution solution;
    cout << solution.maxCoins2(piles) << endl;
    return 0;
}
